home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / pc / HPACK78S.ZIP / crypt / rsa.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-11-28  |  19.6 KB  |  728 lines
  1. /****************************************************************************
  2. *                                                                            *
  3. *                            HPACK Multi-System Archiver                        *
  4. *                            ===========================                        *
  5. *                                                                            *
  6. *                               RSA Library Routines                            *
  7. *                              RSA.C  Updated 18/04/92                        *
  8. *                                                                            *
  9. * This program is protected by copyright and as such any use or copying of    *
  10. *  this code for your own purposes directly or indirectly is highly uncool    *
  11. *                      and if you do so there will be....trubble.                *
  12. *                 And remember: We know where your kids go to school.            *
  13. *                                                                            *
  14. *        Parts copyright 1991  Philip Zimmermann.  Used with permission        *
  15. *          Adapted 1991, 1992  Peter C.Gutmann.  All rights reserved            *
  16. *                                                                            *
  17. ****************************************************************************/
  18.  
  19. #include <string.h>
  20. #ifdef __MAC__
  21.   #include "defs.h"
  22.   #include "rsa.h"
  23. #else
  24.   #include "defs.h"
  25.   #include "crypt/rsa.h"
  26. #endif /* __MAC__ */
  27.  
  28. /* General-purpose encryption buffer, defined in CRYPT.C */
  29.  
  30. extern BYTE *cryptBuffer;
  31.  
  32. /* Level of precision for all routines */
  33.  
  34. int globalPrecision;
  35.  
  36. /****************************************************************************
  37. *                                                                            *
  38. *                            RSA Library Support Routines                    *
  39. *                                                                            *
  40. ****************************************************************************/
  41.  
  42. /* Returns number of significant units in mpReg */
  43.  
  44. int significance( MP_REG *mpReg )
  45.     {
  46.     int precision = globalPrecision;
  47.  
  48.     /* Parse mpReg arschlings */
  49.     mpReg += precision - 1;
  50.     do
  51.         if( *mpReg-- )
  52.             return( precision );
  53.     while( --precision );
  54.  
  55.     return( 0 );
  56.     }
  57.  
  58. /* Begin sniffing at the MSB */
  59.  
  60. WORD bitMask;
  61.  
  62. int initBitSniffer( MP_REG *mpReg )
  63.     {
  64.     int bits, precision = significance( mpReg );
  65.  
  66.     bitMask = 0x8000;
  67.     if( !precision )
  68.         return( 0 );
  69.     bits = units2bits( precision );
  70.     mpReg += precision - 1;
  71.     while( !( *mpReg & bitMask ) )
  72.         {
  73.         bitMask >>= 1;
  74.         bits--;
  75.         }
  76.     return( bits );
  77.     }
  78.  
  79. /* Init multiprecision register mpReg with short value.  Note that mp_init
  80.    doesn't extend sign bit for >32767 */
  81.  
  82. void mp_init( MP_REG *mpReg, WORD value )
  83.     {
  84.     *mpReg++ = value;
  85.     mp_clear( mpReg, globalPrecision - 1 );
  86.     }
  87.  
  88. /* Compares multiprecision registers r1 and r2, and returns -1 if r1 < r2,
  89.    0 if r1 == r2, or +1 if r1 > r2 */
  90.  
  91. static int mp_compare( MP_REG *r1, MP_REG *r2 )
  92.     {
  93.     int precision = globalPrecision;    /* Number of units to compare */
  94.  
  95.     r1 += precision - 1;
  96.     r2 += precision - 1;    /* Point to MSB's of registers */
  97.     do
  98.         {
  99.         if( *r1 < *r2 )
  100.             return( -1 );    /* r1 < r2 */
  101.         if( *r1-- > *r2-- )
  102.             return( 1 );    /* r1 > r2 */
  103.         }
  104.     while( --precision );
  105.  
  106.     return( 0 );            /* r1 == r2 */
  107.     }
  108.  
  109. /* Decrement MP register mpReg */
  110.  
  111. static void mp_dec( MP_REG *mpReg )
  112.     {
  113.     int precision = globalPrecision;    /* Number of units to decrement */
  114.  
  115.     do
  116.         {
  117.         if( ( *mpReg )-- )
  118.             return;
  119.         mpReg++;
  120.         }
  121.     while( --precision );
  122.     }
  123.  
  124. /****************************************************************************
  125. *                                                                            *
  126. *                        Multiprecision Integer Routines                        *
  127. *                                                                            *
  128. ****************************************************************************/
  129.  
  130. #ifndef ASM_RSA
  131.  
  132. static int precMod8, precDiv8;        /* Global precision mod 8, div 8 */
  133.  
  134. /* Set the precision to which MP numbers are calculated */
  135.  
  136. void mp_setp( const int precision )
  137.     {
  138.     int unitPrecision = bits2units( precision );
  139.  
  140.     precMod8 = unitPrecision & 7;
  141.     precDiv8 = unitPrecision >> 3;
  142.     }
  143.  
  144. /* Add one MP number to another */
  145.  
  146. void mp_add( MP_REG *reg1, MP_REG *reg2 )
  147.     {
  148.     int count = precDiv8, carry = 0;
  149.     long value;
  150.  
  151.     switch( precMod8 )
  152.         {
  153.         case 0:
  154.             do {
  155.             value = ( long ) *reg1 + ( long ) *reg2 + carry;
  156.             *reg1 += *reg2 + carry;
  157.             carry = ( value & 0x00010000L ) ? 1 : 0;
  158.             reg1++;
  159.             reg2++;
  160.  
  161.         case 7:
  162.             value = ( long ) *reg1 + ( long ) *reg2 + carry;
  163.             *reg1 += *reg2 + carry;
  164.             carry = ( value & 0x00010000L ) ? 1 : 0;
  165.             reg1++;
  166.             reg2++;
  167.  
  168.         case 6:
  169.             value = ( long ) *reg1 + ( long ) *reg2 + carry;
  170.             *reg1 += *reg2 + carry;
  171.             carry = ( value & 0x00010000L ) ? 1 : 0;
  172.             reg1++;
  173.             reg2++;
  174.  
  175.         case 5:
  176.             value = ( long ) *reg1 + ( long ) *reg2 + carry;
  177.             *reg1 += *reg2 + carry;
  178.             carry = ( value & 0x00010000L ) ? 1 : 0;
  179.             reg1++;
  180.             reg2++;
  181.  
  182.         case 4:
  183.             value = ( long ) *reg1 + ( long ) *reg2 + carry;
  184.             *reg1 += *reg2 + carry;
  185.             carry = ( value & 0x00010000L ) ? 1 : 0;
  186.             reg1++;
  187.             reg2++;
  188.  
  189.         case 3:
  190.             value = ( long ) *reg1 + ( long ) *reg2 + carry;
  191.             *reg1 += *reg2 + carry;
  192.             carry = ( value & 0x00010000L ) ? 1 : 0;
  193.             reg1++;
  194.             reg2++;
  195.  
  196.         case 2:
  197.             value = ( long ) *reg1 + ( long ) *reg2 + carry;
  198.             *reg1 += *reg2 + carry;
  199.             carry = ( value & 0x00010000L ) ? 1 : 0;
  200.             reg1++;
  201.             reg2++;
  202.  
  203.         case 1:
  204.             value = ( long ) *reg1 + ( long ) *reg2 + carry;
  205.             *reg1 += *reg2 + carry;
  206.             carry = ( value & 0x00010000L ) ? 1 : 0;
  207.             reg1++;
  208.             reg2++;
  209.             } while( count-- > 0 );
  210.         }
  211.     }
  212.  
  213. /* Subtract one MP number from another */
  214.  
  215. BOOLEAN mp_sub( MP_REG *reg1, MP_REG *reg2 )
  216.     {
  217.     int count = precDiv8, borrow = 0;
  218.     long value;
  219.  
  220.     switch( precMod8 )
  221.         {
  222.         case 0:
  223.             do {
  224.             value = ( long ) *reg1 - ( long ) ( *reg2 + borrow );
  225.             *reg1 -= *reg2 + borrow;
  226.             borrow = ( value & 0x00010000L ) ? 1 : 0;
  227.             reg1++;
  228.             reg2++;
  229.  
  230.         case 7:
  231.             value = ( long ) *reg1 - ( long ) ( *reg2 + borrow );
  232.             *reg1 -= *reg2 + borrow;
  233.             borrow = ( value & 0x00010000L ) ? 1 : 0;
  234.             reg1++;
  235.             reg2++;
  236.  
  237.         case 6:
  238.             value = ( long ) *reg1 - ( long ) ( *reg2 + borrow );
  239.             *reg1 -= *reg2 + borrow;
  240.             borrow = ( value & 0x00010000L ) ? 1 : 0;
  241.             reg1++;
  242.             reg2++;
  243.  
  244.         case 5:
  245.             value = ( long ) *reg1 - ( long ) ( *reg2 + borrow );
  246.             *reg1 -= *reg2 + borrow;
  247.             borrow = ( value & 0x00010000L ) ? 1 : 0;
  248.             reg1++;
  249.             reg2++;
  250.  
  251.         case 4:
  252.             value = ( long ) *reg1 - ( long ) ( *reg2 + borrow );
  253.             *reg1 -= *reg2 + borrow;
  254.             borrow = ( value & 0x00010000L ) ? 1 : 0;
  255.             reg1++;
  256.             reg2++;
  257.  
  258.         case 3:
  259.             value = ( long ) *reg1 - ( long ) ( *reg2 + borrow );
  260.             *reg1 -= *reg2 + borrow;
  261.             borrow = ( value & 0x00010000L ) ? 1 : 0;
  262.             reg1++;
  263.             reg2++;
  264.  
  265.         case 2:
  266.             value = ( long ) *reg1 - ( long ) ( *reg2 + borrow );
  267.             *reg1 -= *reg2 + borrow;
  268.             borrow = ( value & 0x00010000L ) ? 1 : 0;
  269.             reg1++;
  270.             reg2++;
  271.  
  272.         case 1:
  273.             value = ( long ) *reg1 - ( long ) ( *reg2 + borrow );
  274.             *reg1 -= *reg2 + borrow;
  275.             borrow = ( value & 0x00010000L ) ? 1 : 0;
  276.             reg1++;
  277.             reg2++;
  278.             } while( count-- > 0 );
  279.         }
  280.  
  281.     return( borrow );
  282.     }
  283.  
  284. /* Rotate a MP number */
  285.  
  286. void mp_rotateleft( MP_REG *reg, const BOOLEAN carry )
  287.     {
  288.     int carryIn = carry, carryOut, count = precDiv8;
  289.  
  290.     switch( precMod8 )
  291.         {
  292.         case 0:
  293.             do {
  294.             carryOut = ( *reg & 0x8000 ) ? 1 : 0;
  295.             *reg = ( *reg << 1 ) | carryIn;
  296.             carryIn = carryOut;
  297.             reg++;
  298.  
  299.         case 7:
  300.             carryOut = ( *reg & 0x8000 ) ? 1 : 0;
  301.             *reg = ( *reg << 1 ) | carryIn;
  302.             carryIn = carryOut;
  303.             reg++;
  304.  
  305.         case 6:
  306.             carryOut = ( *reg & 0x8000 ) ? 1 : 0;
  307.             *reg = ( *reg << 1 ) | carryIn;
  308.             carryIn = carryOut;
  309.             reg++;
  310.  
  311.         case 5:
  312.             carryOut = ( *reg & 0x8000 ) ? 1 : 0;
  313.             *reg = ( *reg << 1 ) | carryIn;
  314.             carryIn = carryOut;
  315.             reg++;
  316.  
  317.         case 4:
  318.             carryOut = ( *reg & 0x8000 ) ? 1 : 0;
  319.             *reg = ( *reg << 1 ) | carryIn;
  320.             carryIn = carryOut;
  321.             reg++;
  322.  
  323.         case 3:
  324.             carryOut = ( *reg & 0x8000 ) ? 1 : 0;
  325.             *reg = ( *reg << 1 ) | carryIn;
  326.             carryIn = carryOut;
  327.             reg++;
  328.  
  329.         case 2:
  330.             carryOut = ( *reg & 0x8000 ) ? 1 : 0;
  331.             *reg = ( *reg << 1 ) | carryIn;
  332.             carryIn = carryOut;
  333.             reg++;
  334.  
  335.         case 1:
  336.             carryOut = ( *reg & 0x8000 ) ? 1 : 0;
  337.             *reg = ( *reg << 1 ) | carryIn;
  338.             carryIn = carryOut;
  339.             reg++;
  340.             } while( count-- > 0 );
  341.         }
  342.     }
  343. #endif /* !ASM_RSA */
  344.  
  345. /****************************************************************************
  346. *                                                                            *
  347. *                            RSA Signature-Check Routine                        *
  348. *                                                                            *
  349. ****************************************************************************/
  350.  
  351. /* Charlie Merritt's MODMULT algorithm as implemented by Phil Zimmerman,
  352.    refined by Zhahai Stewart to reduce the number of subtracts, and hacked by
  353.    Peter Gutmann. It performs a multiply combined with a modulo operation,
  354.    without going into "double precision".  It is faster than the generic
  355.    peasant method and still works well on machines that lack a fast hardware
  356.    multiply instruction */
  357.  
  358. /*    Shift r1 one whole unit to the left */
  359.  
  360. static void mp_shiftleftUnit( MP_REG *r1 )
  361.     {
  362.     int precision = globalPrecision;
  363.     MP_REG *r2;
  364.  
  365.     r1 += precision - 1;    /* Point to end of register */
  366.     r2 = r1;
  367.     while( --precision )
  368.         *r1-- = *--r2;
  369.     *r1 = 0;
  370.     }
  371.  
  372. /* Preshifted images of the modulus, and the multiplicand mod n */
  373.  
  374. static MP_REG *moduliBuffer;
  375. static MP_REG *mpdBuffer;
  376.  
  377. /* To optimize msubs, we need the following 2 unit arrays, each filled with
  378.    the most significant unit and next-most significant unit of the preshifted
  379.    images of the modulus */
  380.  
  381. static MP_REG msUnitModuli[ UNITSIZE + 1 ];        /* Most sig. unit */
  382. static MP_REG nmsUnitModuli[ UNITSIZE + 1 ];    /* Next-most sig. unit */
  383.  
  384. /* The following macro is used to calculate indices into the MP buffers, and
  385.    is needed because of C's difficulty with handling dynamically allocated
  386.    multidimensional arrays */
  387.  
  388. #define MP(i)    ( ( i ) * MAX_UNIT_PRECISION )
  389.  
  390. /* Computes UNITSIZE preshifted images of r1, each shifted left 1 more bit */
  391.  
  392. static void stageMPimages( MP_REG *r1 )
  393.     {
  394.     int i;
  395.     MP_REG *mpdBufPtr;    /* Pointer to address in mpdBuffer */
  396.  
  397.     /* Use cryptBuffer as scratch space */
  398.     mpdBuffer = ( MP_REG * ) cryptBuffer;
  399.  
  400.     /* Copy in first image */
  401.     mp_move( mpdBuffer, r1 );
  402.  
  403.     /* Compute the preshifted images */
  404.     for( i = 1; i < UNITSIZE; i++ )
  405.         {
  406.         mpdBufPtr = mpdBuffer + MP( i );
  407.         mp_move( mpdBufPtr, mpdBuffer + MP( i - 1 ) );
  408.         mp_shiftleft( mpdBufPtr );
  409.         }
  410.     }
  411.  
  412. /* Compute UNITSIZE + 1 images of modulus, each shifted left 1 more bit.
  413.    Before calling mp_modmult, we must first stage the moduli images by
  414.    calling stageModulus().  Assumes that global_precision has already been
  415.    adjusted to the size of the modulus, plus SLOP_BITS */
  416.  
  417. void stageModulus( MP_REG *modulus )
  418.     {
  419.     int i;
  420.     MP_REG *modBufPtr;    /* Pointer to address in moduliBuffer */
  421.  
  422.     /* Use more of cryptBuffer as scratch space */
  423.     moduliBuffer = ( MP_REG * ) cryptBuffer + ( UNITSIZE * MAX_UNIT_PRECISION );
  424.  
  425.     /* Set up table for use by msubs macro; first do zero'th element */
  426.     mp_move( moduliBuffer, modulus );
  427.     modulus += globalPrecision - 1;
  428.     msUnitModuli[ 0 ] = *modulus--;
  429.     nmsUnitModuli[ 0 ] = *modulus;
  430.  
  431.     /* Now do rest of table */
  432.     for( i = 1; i < UNITSIZE + 1; i++ )
  433.         {
  434.         modBufPtr = moduliBuffer + MP( i );
  435.         mp_move( modBufPtr, moduliBuffer + MP( i - 1 ) );
  436.         mp_shiftleft( modBufPtr );
  437.         modBufPtr += globalPrecision - 1;
  438.         msUnitModuli[ i ] = *modBufPtr--;
  439.         nmsUnitModuli[ i ] = *modBufPtr;
  440.         }
  441.     }
  442.  
  443. #define sniffAdd(i)    if( *multiplier & ( 1 << i ) ) \
  444.                         mp_add( product, mpdBuffer + MP( i ) )
  445.  
  446. /* To optimize msubs, compare the most significant units of the product and
  447.    the shifted modulus before deciding to call the full mp_compare routine.
  448.    Better still, compare the upper two units before deciding to call mp_compare */
  449.  
  450. #define msubs(i)    if( ( ( p_m = *msUnitProduct - msUnitModuli[ i ] ) > 0 ) || \
  451.                         ( !p_m && ( ( *nmsUnitProduct > nmsUnitModuli[ i ] ) || \
  452.                           ( ( *nmsUnitProduct == nmsUnitModuli[ i ] ) && \
  453.                             ( ( mp_compare( product, moduliBuffer + MP( i ) ) >= 0 ) ) ) ) ) ) \
  454.                         mp_sub( product, moduliBuffer + MP( i ) )
  455.  
  456. /*    Performs combined multiply/modulo operation. Computes:
  457.     product = ( multiplicand * multiplier ) mod modulus */
  458.  
  459. void mp_modmult( MP_REG *product, MP_REG *multiplicand, MP_REG *multiplier )
  460.     {
  461.     /* p_m, msUnitProduct, and nmsUnitProduct are used by the msubs macro */
  462.     int p_m;
  463.     MP_REG *msUnitProduct;    /* Pointer to most significant unit of product */
  464.     MP_REG *nmsUnitProduct;    /* Next-most signif. unit of product */
  465.     int multPrec;            /* Precision of multiplier, in units */
  466.  
  467.     /* Compute preshifted images of multiplicand, mod n */
  468.     stageMPimages( multiplicand );
  469.  
  470.     /* To optimize msubs, set up msUnitProduct and nmsUnitProduct as pointers
  471.        to MSU and next-MSU of product */
  472.     msUnitProduct = product + globalPrecision - 1;
  473.     nmsUnitProduct = msUnitProduct - 1;
  474.  
  475.     /* To understand this algorithm, it would be helpful to first study the
  476.        conventional generic peasant (aka Edouard) modmult algorithm.  This
  477.        one does about the same thing as generic peasant, but is organized
  478.        differently to save some steps.  It loops through the multiplier a
  479.        word (unit) at a time, instead of a bit at a time.  It word-shifts the
  480.        product instead of bit-shifting it, so it should be faster.  It also
  481.        does about half as many subtracts as the generic peasant algorithm */
  482.     mp_init( product, 0 );            /* Set product to 0 */
  483.  
  484.     /* Normalize and compute number of units in multiplier first: */
  485.     multPrec = significance( multiplier );
  486.     multiplier += multPrec - 1;    /* Start at MSU of multiplier */
  487.  
  488.     /* Loop for the number of units in the multiplier */
  489.     while( multPrec-- )
  490.         {
  491.         /*    Shift the product one whole unit to the left.  This is part of
  492.             the multiply phase of modmult */
  493.         mp_shiftleftUnit( product );
  494.  
  495.         /* Sniff each bit in the current unit of the multiplier, and
  496.            conditionally add the the corresponding preshifted image of the
  497.            multiplicand to the product.  This is also part of the multiply
  498.            phase of modmult.  The following loop is unrolled for speed,
  499.            using macros:
  500.  
  501.            for( i = UNITSIZE - 1; i >= 0; i-- )
  502.               if( *multiplier & ( 1 << i ) )
  503.                  mp_add( product, mpdBuffer[ i ] ); */
  504.         sniffAdd( 15 );
  505.         sniffAdd( 14 );
  506.         sniffAdd( 13 );
  507.         sniffAdd( 12 );
  508.         sniffAdd( 11 );
  509.         sniffAdd( 10 );
  510.         sniffAdd( 9 );
  511.         sniffAdd( 8 );
  512.         sniffAdd( 7 );
  513.         sniffAdd( 6 );
  514.         sniffAdd( 5 );
  515.         sniffAdd( 4 );
  516.         sniffAdd( 3 );
  517.         sniffAdd( 2 );
  518.         sniffAdd( 1 );
  519.         sniffAdd( 0 );
  520.  
  521.         /* The product may have grown by as many as UNITSIZE + 1 bits.
  522.            That's why we have globalPrecision set to the size of the modulus
  523.            plus UNITSIZE + 1 slop bits.  Now reduce the product back down by
  524.            conditionally subtracting the UNITSIZE + 1 preshifted images of
  525.            the modulus.  This is the modulo reduction phase of modmult.  The
  526.            following loop is unrolled for speed, using macros:
  527.  
  528.            for( i = UNITSIZE; i >= 0; i-- )
  529.               if( mp_compare( product, moduliBuffer[ i ] ) >= 0 )
  530.                  mp_sub( product, moduliBuffer[ i ] ); */
  531.         msubs( 16 );
  532.         msubs( 15 );
  533.         msubs( 14 );
  534.         msubs( 13 );
  535.         msubs( 12 );
  536.         msubs( 11 );
  537.         msubs( 10 );
  538.         msubs( 9 );
  539.         msubs( 8 );
  540.         msubs( 7 );
  541.         msubs( 6 );
  542.         msubs( 5 );
  543.         msubs( 4 );
  544.         msubs( 3 );
  545.         msubs( 2 );
  546.         msubs( 1 );
  547.         msubs( 0 );
  548.  
  549.         /* Bump pointer to next lower unit of multiplier */
  550.         multiplier--;
  551.         }
  552.     }
  553.  
  554. /* Generic peasant combined exponentiation/modulo algorithm.  Calls modmult
  555.    instead of mult.  Computes: expout = ( expin ** exponent ) mod modulus */
  556.  
  557. #define sniffBit(exp)        ( *( exp ) & bitMask )
  558. #define bumpBitSniffer(exp)    if( !( bitMask >>= 1 ) ) \
  559.                                 { \
  560.                                 bitMask = 0x8000; \
  561.                                 exp--; \
  562.                                 }
  563.  
  564. void mp_modexp( MP_REG *expOut, MP_REG *expIn, MP_REG *exponent, MP_REG *modulus )
  565.     {
  566.     int bits;
  567.     int savedPrecision = globalPrecision;
  568.     MP_REG product[ MAX_UNIT_PRECISION ];
  569.  
  570.     /* Clear output register at full precision before we reset it to the
  571.        smallest optimum precision */
  572.     mp_clear( expOut, globalPrecision );
  573.  
  574.     /* Set smallest optimum precision for this modulus and set up preshifted
  575.        images of the modulus */
  576.     setPrecision( bits2units( countbits( modulus ) + SLOP_BITS ) );
  577.     stageModulus( modulus );
  578.  
  579.     /* Compute number of bits in exponent and normalize it */
  580.     bits = initBitSniffer( exponent );
  581.     normalize( exponent );
  582.  
  583.     /* We can optimize out the first modsquare and modmult since we know for
  584.        sure at this point that bits > 0 */
  585.     bits--;
  586.     bumpBitSniffer( exponent );
  587.     mp_move( expOut, expIn );        /* expOut = ( 1 * 1 ) * expin */
  588.  
  589.     while( bits-- )
  590.         {
  591.         mp_modsquare( product, expOut );
  592.         mp_move( expOut, product );
  593.  
  594.         if( sniffBit( exponent ) )
  595.             {
  596.             mp_modmult( product, expOut, expIn );
  597.             mp_move( expOut, product );
  598.             }
  599.         bumpBitSniffer( exponent );
  600.         }
  601.     setPrecision( savedPrecision );    /* Restore original precision */
  602.  
  603.     /* Destroy sensitive data */
  604.     mp_burn( product, MAX_UNIT_PRECISION );
  605.     mp_burn( msUnitModuli, UNITSIZE + 1 );
  606.     mp_burn( nmsUnitModuli, UNITSIZE + 1 );
  607.     }
  608.  
  609. /****************************************************************************
  610. *                                                                            *
  611. *                                RSA Decryption Routine                        *
  612. *                                                                            *
  613. ****************************************************************************/
  614.  
  615. /* Generic peasant multiply algorithm */
  616.  
  617. static void mp_mult( MP_REG *product, MP_REG *multiplicand, MP_REG *multiplier)
  618.     {
  619.     int bits;
  620.  
  621.     mp_init( product, 0 );
  622.     if( testEq( multiplicand, 0 ) )
  623.         /* Multiplying by zero gives zero */
  624.         return;
  625.  
  626.     /* Compute number of bits in multiplier and normalize it */
  627.     bits = initBitSniffer( multiplier );
  628.     normalize( multiplier );
  629.     while( bits-- )
  630.         {
  631.         mp_shiftleft( product );
  632.         if( sniffBit( multiplier ) )
  633.             mp_add( product, multiplicand );
  634.         bumpBitSniffer( multiplier );
  635.         }
  636.     }
  637.  
  638. /* Unsigned divide routine */
  639.  
  640. static void mp_mod( MP_REG *remainder, MP_REG *dividend, MP_REG *divisor )
  641.     {
  642.     int bits;
  643.  
  644.     mp_init( remainder, 0 );
  645.  
  646.     /* Compute number of bits in dividend and normalize it */
  647.     bits = initBitSniffer( dividend );
  648.     normalize( dividend );
  649.     while( bits-- )
  650.         {
  651.         mp_rotateleft( remainder, ( sniffBit( dividend ) != 0 ) ? 1 : 0 );
  652.         if( mp_compare( remainder, divisor ) >= 0 )
  653.             mp_sub( remainder, divisor );
  654.         bumpBitSniffer( dividend );
  655.         }
  656.     }
  657.  
  658. /* Use the Chinese Remainder Theorem shortcut for RSA decryption.
  659.    M is the output plaintext message, C is the input ciphertext message,
  660.    d is the secret decryption exponent, p and q are the prime factors of n,
  661.    u is the multiplicative inverse of q, mod p.  n, the common modulus, is not
  662.    used because of the Chinese Remainder Theorem shortcut */
  663.  
  664. void rsaDecrypt( MP_REG *M, MP_REG *C, MP_REG *d, MP_REG *p, MP_REG *q, MP_REG *u )
  665.     {
  666.     MP_REG p2[ MAX_UNIT_PRECISION ], q2[ MAX_UNIT_PRECISION ];
  667.     MP_REG temp1[ MAX_UNIT_PRECISION ], temp2[ MAX_UNIT_PRECISION ];
  668.  
  669.     /* Initialize result in case of error */
  670.     mp_init( M, 1 );
  671.  
  672.     /* Make sure that p < q */
  673.     if( mp_compare( p, q ) >= 0 )
  674.         {
  675.         /* Swap the pointers p and q */
  676.         MP_REG *tmp = p;
  677.         p = q; q = tmp;
  678.         }
  679.  
  680.     /* Rather than decrypting by computing modexp with full mod n precision,
  681.        compute a shorter modexp with mod p precision:
  682.  
  683.        p2 = [ ( C mod p ) ** ( d mod ( p - 1 ) ) ] mod p */
  684.     mp_move( temp1, p );
  685.     mp_dec( temp1 );            /* temp1 = p - 1 */
  686.     mp_mod( temp2, d, temp1 );    /* temp2 = d mod ( p - 1 ) ) */
  687.     mp_mod( temp1, C, p );        /* temp1 = C mod p  */
  688.     mp_modexp( p2, temp1, temp2, p );
  689.  
  690.     /* Now compute a short modexp with mod q precision:
  691.  
  692.        q2 = [ ( C mod q ) ** ( d mod ( q - 1 ) ) ] mod q */
  693.     mp_move( temp1, q );
  694.     mp_dec( temp1 );            /* temp1 = q - 1 */
  695.     mp_mod( temp2, d, temp1 );    /* temp2 = d mod ( q - 1 ) */
  696.     mp_mod( temp1, C, q );        /* temp1 = C mod q  */
  697.     mp_modexp( q2, temp1, temp2, q );
  698.  
  699.     /* Now use the multiplicative inverse u to glue together the two halves,
  700.        saving a lot of time by avoiding a full mod n exponentiation.  At key
  701.        generation time, u was computed with the secret key as the
  702.        multiplicative inverse of p, mod q such that ( p * u ) mod q = 1,
  703.        assuming p < q */
  704.     if( mp_compare( p2, q2 ) == 0 )
  705.         /* Only happens if C < p */
  706.         mp_move( M, p2 );
  707.     else
  708.         {
  709.         /* q2 = q2 - p2; if q2 < 0 then q2 = q2 + q */
  710.         if( mp_sub( q2, p2 ) )
  711.             /* If the result went negative, add q to q2 */
  712.             mp_add( q2, q );
  713.  
  714.         /* M = p2 + ( p * [ ( q2 * u ) mod q ] ) */
  715.         mp_mult( temp1, q2, u );    /* temp1 = q2 * u  */
  716.         mp_mod( temp2, temp1, q );    /* temp2 = temp1 mod q */
  717.         mp_mult( temp1, p, temp2 );    /* temp1 = p * temp2 */
  718.         mp_add( temp1, p2 );        /* temp1 = temp1 + p2 */
  719.         mp_move( M, temp1 );        /* M = temp1 */
  720.         }
  721.  
  722.     /* Destroy sensitive data */
  723.     mp_burn( p2, MAX_UNIT_PRECISION );
  724.     mp_burn( q2, MAX_UNIT_PRECISION );
  725.     mp_burn( temp1, MAX_UNIT_PRECISION );
  726.     mp_burn( temp2, MAX_UNIT_PRECISION );
  727.     }
  728.